Advent of Code Day 21 - Part 1 You find a program trying to generate some art. It uses a strange process that involves repeatedly enhancing the detail of an image through a set of rules.
The image consists of a two-dimensional square grid of pixels that are either on (#) or off (.). The program always begins with this pattern:
.#. ..#
Because the pattern is both 3 pixels wide and 3 pixels tall, it is said to have a size of 3.
Then, the program repeats the following process:
If the size is evenly divisible by 2, break the pixels up into 2x2 squares, and convert each 2x2 square into a 3x3 square by following the corresponding enhancement rule. Otherwise, the size is evenly divisible by 3; break the pixels up into 3x3 squares, and convert each 3x3 square into a 4x4 square by following the corresponding enhancement rule. Because each square of pixels is replaced by a larger one, the image gains pixels and so its size increases.
The artist's book of enhancement rules is nearby (your puzzle input); however, it seems to be missing rules. The artist explains that sometimes, one must rotate or flip the input pattern to find a match. (Never rotate or flip the output pattern, though.) Each pattern is written concisely: rows are listed as single units, ordered top-down, and separated by slashes. For example, the following rules correspond to the adjacent patterns:
../.# = .. .#
.#.
.#./..#/### = ..#
###
#..#
#..#
.##.
When searching for a rule to use, rotate and flip the pattern as necessary. For example, all of the following patterns match the same rule:
.#. .#. #.. ### ..# #.. #.# ..#
Suppose the book contained the following two rules:
../.# => ##./#../... .#./..#/### => #..#/..../..../#..# As before, the program begins with this pattern:
.#. ..#
The size of the grid (3) is not divisible by 2, but it is divisible by 3. It divides evenly into a single square; the square matches the second rule, which produces:
.... ....
The size of this enhanced grid (4) is evenly divisible by 2, so that rule is used. It divides evenly into four squares:
..|.. --+-- ..|..
Each of these squares matches the same rule (../.# => ##./#../...), three of which require some flipping and rotation to line up with the rule. The output for the rule is the same in all four cases:
...|... ---+---
...|... Finally, the squares are joined into a new grid:
......
...... Thus, after 2 iterations, the grid contains 12 pixels that are on.
How many pixels stay on after 5 iterations?
In [ ]:
# Setup the rules
path = 'day21a.txt'
with open(path, 'r') as file:
content = file.read().splitlines()
tworule, threerule = {}, {}
for key, value in enumerate(content):
infrom = content[key].rsplit('=>')[0].replace(" ", "")
outto = content[key].rsplit('=>')[1].replace(" ", "")
if (len(infrom)) == 5:
# add to tworule
tworule[infrom] = outto
elif (len(infrom)) == 11:
#add to threerule
threerule[infrom] = outto
print(tworule.keys())
print(threerule.keys())
# TODO: Either make everything an array or everything a string
In [ ]:
def getOutput3(charm, rules, size):
if charm in rules:
return(rules[charm])
# 2 ghi\def\abc
charm2 = charm[-size:] +'/'+charm[size+1:-(size+1)] +'/'+ charm[:size]
# print("2: ",charm2)
if charm2 in rules:
return(rules[charm2])
# 3 cba\fed\cba
charm3 = charm[:size][::-1] +'/'+ charm[size+1:-(size+1)][::-1] +'/'+ charm[-size:][::-1]
# print("3: ",charm3)
if charm3 in rules:
return(rules[charm3])
# 4 gda\heb\ifc
charm4 = charm[8]+ charm[4]+charm[0]+'/'+ charm[9]+ charm[5]+charm[1] + '/'+ charm[10]+ charm[6]+charm[2]
# print("4: ",charm4)
if charm4 in rules:
return(rules[charm4])
# 5 ihg\fed\cba
charm5 = charm[-size:][::-1] +'/'+ charm[size+1:-(size+1)][::-1] +'/'+ charm[:size][::-1]
# print("5: ",charm5)
if charm5 in rules:
return(rules[charm5])
# 6 cfi/beh/adg
charm6 = charm[2]+ charm[6]+charm[10]+'/'+ charm[1]+ charm[5]+charm[9] + '/'+ charm[0]+ charm[4]+charm[8]
# print("6: ",charm6)
if charm6 in rules:
return(rules[charm6])
return("Houston we have a problem")
def getOutput2(charm, rules, size):
if charm in rules:
return(rules[charm])
# 2 cd/ab
charm2 = charm[-size:] +'/'+ charm[:size]
# print("2: ",charm2)
if charm2 in rules:
return(rules[charm2])
# 3 ba/dc
charm3 = charm[:size][::-1] +'/'+ charm[-size:][::-1]
# print("3: ",charm3)
if charm3 in rules:
return(rules[charm3])
# 4 dc/ba
charm4 = charm[-size:][::-1] +'/'+ charm[:size][::-1]
# print("4: ",charm4)
if charm4 in rules:
return(rules[charm4])
# 5 ca/db
charm5 = charm[3] + charm[0] +'/'+ charm[4] + charm[1]
# print("5: ",charm5)
if charm5 in rules:
return(rules[charm5])
# 6 bd/ac
charm6 = charm[1] + charm[4] +'/'+ charm[0] + charm[3]
# print("6: ",charm6)
if charm6 in rules:
return(rules[charm6])
return("Houston we have a problem")
In [ ]:
def oldenhanceart(art, rules, size):
#divide up the grid
charm = ''
gridsize = len(art)
newgridsize = int(gridsize + gridsize/size )
newart = [[off for x in range(newgridsize)] for y in range(newgridsize)]
for group in range(int((gridsize/size)**2)):
print(" * Start processing Group ", group, " of ",(gridsize/size)**2, " to ", newgridsize )
charm = ''
#This is wrong
for x in range(size):
charm = art[]
print(" This is X ", x, art[x][:size])
print(" This is group ", group, art[group][:size])
charm = charm + ''.join(art[x][:size]) + '/'
charm = charm[:-1]
print(" - The Charm:", charm)
if size == 3:
output = getOutput3(charm, rules, size)
else:
output = getOutput2(charm, rules, size)
print(" - The output: ", output)
for keyx, valuex in enumerate(output.rsplit('/')):
for keyy, valuey in enumerate(valuex):
print(" - Keyx, keyy, valuey ", keyx, keyy, valuey)
newart[keyx][keyy] = valuey
return(newart)
In [ ]:
def enhanceart(art, rules, size):
#divide up the grid
charm = ''
gridsize = len(art)
newgridsize = int(gridsize + gridsize/size )
newart = [[off for x in range(newgridsize)] for y in range(newgridsize)]
myout = []
if gridsize % 2 == 0:
for y in range(0, gridsize, 2):
for x in range(0, gridsize, 2):
#print(art[y][x:x+2], art[y+1][x:x+2])
charm = ''.join(art[y][x:x+2]) + '/' + ''.join(art[y+1][x:x+2])
output = getOutput2(charm, rules, 2)
myout.append(output)
c = 0
for y in range(0, gridsize, 3):
for x in range(0, gridsize, 3):
newart[y][x:x+3] = myout[c].split('/')[0]
newart[y+1][x:x+3] = myout[c].split('/')[1]
newart[y+2][x:x+3] = myout[c].split('/')[2]
c = c + 1
elif gridsize % 3 == 0:
for y in range(0, gridsize, 3):
for x in range(0, gridsize, 3):
# print(art[y][x:x+3], art[y+1][x:x+3], art[y+2][x:x+3])
charm = ''.join(art[y][x:x+3]) + '/' + ''.join(art[y+1][x:x+3]) + '/' + ''.join(art[y+2][x:x+3])
print(charm)
output = getOutput3(charm, rules, 3)
# This still might be wrong. May need to do above
for keyx, valuex in enumerate(output.rsplit('/')):
for keyy, valuey in enumerate(valuex):
# print(" - Keyx, keyy, valuey ", keyx, keyy, valuey)
newart[keyx][keyy] = valuey
else:
print("Grid size is off ")
return(newart)
In [ ]:
# Setup initial grid
on = '#'
off = '.'
art = [[off for x in range(3)] for y in range(3)]
art[0][1], art[1][2] = on, on
for i in range(3):
art[2][i] = on
print(art)
# TODO: Either make everything an array or everything a string
In [ ]:
strokes = 5 # puzzle iteration
# strokes = 2 # sample iteration
for z in range(strokes):
print('In: ', art)
if (len(art) % 2) == 0:
# ehance art by rule
art = enhanceart(art, tworule, 2)
elif (len(art) % 3) == 0:
# ehance art by rule
art = enhanceart(art, threerule, 3)
else:
print("There is a problem with your art ")
print("out: ", art)
print(" ")
total = 0
for x in art:
total = total + x.count('#')
print(total)
What I learned on day 21
Advent of Code Day 19
Advent of Code Day 19 - Part 1 --- Day 19: A Series of Tubes --- Somehow, a network packet got lost and ended up here. It's trying to follow a routing diagram (your puzzle input), but it's confused about where to go.
Its starting point is just off the top of the diagram. Lines (drawn with |, -, and +) show the path it needs to take, starting by going down onto the only line connected to the top of the diagram. It needs to follow this path until it reaches the end (located somewhere within the diagram) and stop there.
Sometimes, the lines cross over each other; in these cases, it needs to continue going the same direction, and only turn left or right when there's no other option. In addition, someone has left letters on the line; these also don't change its direction, but it can use them to keep track of where it's been. For example:
|
| +--+
A | C
F---|----E|--+ | | | D +B-+ +--+
Given this diagram, the packet needs to take the following path:
Starting at the only line touching the top of the diagram, it must go down, pass through A, and continue onward to the first +. Travel right, up, and right, passing through B in the process. Continue down (collecting C), right, and up (collecting D). Finally, go all the way left through E and stopping at F. Following the path to the end, the letters it sees on its path are ABCDEF.
The little packet looks up at you, hoping you can help it find the way. What letters will it see (in the order it would see them) if it follows the path? (The routing diagram is very wide; make sure you view it without line wrapping.)
In [ ]:
path = 'day19a.txt'
with open(path, 'r') as file:
content = file.read().splitlines()
for line in content:
print(line)
In [ ]:
print(content[0][5])
In [ ]:
** Advent of Code Day 18 - Part 1 ** You discover a tablet containing some strange assembly code labeled simply "Duet". Rather than bother the sound card with it, you decide to run the code yourself. Unfortunately, you don't see any documentation, so you're left to figure out what the instructions mean on your own.
It seems like the assembly is meant to operate on a set of registers that are each named with a single letter and that can each hold a single integer. You suppose each register should start with a value of 0.
There aren't that many instructions, so it shouldn't be hard to figure out what they do. Here's what you determine:
snd X plays a sound with a frequency equal to the value of X.
set X Y sets register X to the value of Y.
add X Y increases register X by the value of Y.
mul X Y sets register X to the result of multiplying the value contained in register X by the value of Y.
mod X Y sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
rcv X recovers the frequency of the last sound played, but only when the value of X is not zero. (If it is zero, the command does nothing.)
jgz X Y jumps with an offset of the value of Y, but only if the value of X is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)
Many of the instructions can take either a register (a single letter) or a number. The value of a register is the integer it contains; the value of a number is that number.
After each jump instruction, the program continues with the instruction to which the jump jumped. After any other instruction, the program continues with the next instruction. Continuing (or jumping) off either end of the program terminates it.
For example:
set a 1
add a 2
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2
The first four instructions set a to 1, add 2 to it, square it, and then set it to itself modulo 5, resulting in a value of 4.
Then, a sound with frequency 4 (the value of a) is played.
After that, a is set to 0, causing the subsequent rcv and jgz instructions to both be skipped (rcv because a is 0, and jgz because a is not greater than 0).
Finally, a is set to 1, causing the next jgz instruction to activate, jumping back two instructions to another jump, which jumps again to the rcv, which ultimately triggers the recover operation.
At the time the recover operation is executed, the frequency of the last sound played is 4.
What is the value of the recovered frequency (the value of the most recently played sound) the first time a rcv instruction is executed with a non-zero value?
To begin, get your puzzle input.
In [ ]:
import string
path = 'day18a.txt'
with open(path, 'r') as file:
content = file.read().split('\n')
print(content)
print(len(content))
In [ ]:
registers = {}
# get all the registers
for line in content:
registers[(line.split(' ')[1])] = 0
print(registers)
frequency = 0
# loop through the instructions
x = 0
while x < len(content) and x > -1:
line = content[x]
chop = line.split(' ')
instruction = chop[0]
reg = chop[1]
if len(chop) > 2:
try:
value = int(chop[2])
except:
value = int(registers[chop[2]])
#print("Process this ", line, " == ", instruction, reg, value)
if instruction == 'snd':
frequency = registers[reg]
elif instruction == 'set':
registers[reg] = int(value)
elif instruction == 'add':
registers[reg] = registers[reg] + (value)
elif instruction == 'mul':
registers[reg] = registers[reg] * value
elif instruction == 'mod':
registers[reg] = registers[reg] % (value)
elif instruction == 'rcv':
if registers[reg] != 0:
registers[reg] = frequency
x = -5
elif instruction == 'jgz':
if registers[reg] > 0:
x = x + (value) - 1
# print("JUMP: ", x, value)
else:
print("Something wrong with the instruction ", instruction )
x = x + 1
# print("The new value of X is ", x )
print(" The value is ", frequency)
Advent of Code Day 18 - Part 2 As you congratulate yourself for a job well done, you notice that the documentation has been on the back of the tablet this entire time. While you actually got most of the instructions correct, there are a few key differences. This assembly code isn't about sound at all - it's meant to be run twice at the same time.
Each running copy of the program has its own set of registers and follows the code independently - in fact, the programs don't even necessarily run at the same speed. To coordinate, they use the send (snd) and receive (rcv) instructions:
snd X sends the value of X to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent. rcv X receives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent. Each program also has its own program ID (one 0 and the other 1); the register p should begin with this value.
For example:
snd 1 snd 2 snd p rcv a rcv b rcv c rcv d Both programs begin by sending three values to the other. Program 0 sends 1, 2, 0; program 1 sends 1, 2, 1. Then, each program receives a value (both 1) and stores it in a, receives another value (both 2) and stores it in b, and then each receives the program ID of the other program (program 0 receives 1; program 1 receives 0) and stores it in c. Each program now sees a different value in its own copy of register c.
Finally, both programs try to rcv a fourth time, but no data is waiting for either of them, and they reach a deadlock. When this happens, both programs terminate.
It should be noted that it would be equally valid for the programs to run at different speeds; for example, program 0 might have sent all three values and then stopped at the first rcv before program 1 executed even its first instruction.
Once both of your programs have terminated (regardless of what caused them to do so), how many times did program 1 send a value? (2000 too low) (9000 is too high)
In [ ]:
import string
path = 'day18.txt'
with open(path, 'r') as file:
content = file.read().split('\n')
print(content)
print(len(content))
In [ ]:
# Build the inputs
oneregisters, zeroregisters = {}, {}
# get all the registers
for line in content:
zeroregisters[(line.split(' ')[1])] = 0
oneregisters[(line.split(' ')[1])] = 0
oneregisters['p'] = 1
print(zeroregisters)
print(oneregisters)
In [ ]:
def processInstruction(chop, registers):
instruction = chop[0]
reg = chop[1] # Not sure what to do with the 1
if len(chop) > 2:
try:
value = int(chop[2])
except:
value = int(registers[chop[2]])
if instruction == 'set':
registers[reg] = int(value)
elif instruction == 'add':
registers[reg] = registers[reg] + (value)
elif instruction == 'mul':
registers[reg] = registers[reg] * value
elif instruction == 'mod':
registers[reg] = registers[reg] % (value)
else:
print("I got to processInstructions wrong ")
return(registers)
In [ ]:
ins = 7
chop = content[ins].split(' ')
print(chop)
zero = []
oneq = []
In [ ]:
Advent of Code Day 16 - Part1 You come upon a very unusual sight; a group of programs here appear to be dancing.
There are sixteen programs in total, named a through p. They start by standing in a line: a stands in position 0, b stands in position 1, and so on until p, which stands in position 15.
The programs' dance consists of a sequence of dance moves:
Spin, written sX, makes X programs move from the end to the front, but maintain their order otherwise. (For example, s3 on abcde produces cdeab). Exchange, written xA/B, makes the programs at positions A and B swap places. Partner, written pA/B, makes the programs named A and B swap places. For example, with only five programs standing in a line (abcde), they could do the following dance:
s1, a spin of size 1: eabcd. x3/4, swapping the last two programs: eabdc. pe/b, swapping programs e and b: baedc. After finishing their dance, the programs end up in order baedc.
You watch the dance for a while and record their dance moves (your puzzle input). In what order are the programs standing after their dance?
In [ ]:
# note: dancepartners key a to p and the value tells you where they are
import string
path = 'day16.txt'
with open(path, 'r') as file:
content = file.read().split(',')
In [ ]:
def parseinstruction(ins):
move = ins[0]
if '/' in ins:
if move == 'p':
# print("in ", dp)
# print(" chars of ", ins[1:].rsplit('/')[0], ins[1:].rsplit('/')[1])
here = dp.index(ins[1:].rsplit('/')[0])
there = dp.index(ins[1:].rsplit('/')[1])
# print(" are they at ", here, there )
elif move == 'x':
here = int(ins[1:].rsplit('/')[0])
there = int(ins[1:].rsplit('/')[1])
else:
here = int(ins[1:])
there = 0
return (move, here, there)
def dotheSpin(move):
global dp
front = dp[(len(dp) - move):]
back = dp[:(len(dp) - move)]
dp = front + back
return()
def dotheExchange(here, there): # This will be better taking 2 parms
global dp
a,b = dp[here], dp[there]
dp[here], dp[there] = b, a
return()
def dothePartner(ins):
return()
In [ ]:
dp = list(range(16))
dp = ['a', 'b', 'c', 'd', 'e']
dp = ['a', 'b', 'c', 'd', 'e','f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
# print(dp)
for key, value in enumerate(content):
move, here, there = parseinstruction(value)
if move == 's':
dotheSpin(here)
elif move == 'x':
dotheExchange(here, there)
elif move == 'p': # they are the same in a 0-15 array
dotheExchange(here, there)
else:
print("There is a problem readint the file ", value)
print("Order of Program: ", dp)
x = ''
for i in dp:
x = x + i
print(x)
Advent of Code Day 16 - Part2 Now that you're starting to get a feel for the dance moves, you turn your attention to the dance as a whole.
Keeping the positions they ended up in from their previous dance, the programs perform it again and again: including the first dance, a total of one billion (1000000000) times.
In the example above, their second dance would begin with the order baedc, and use the same dance moves:
s1, a spin of size 1: cbaed. x3/4, swapping the last two programs: cbade. pe/b, swapping programs e and b: ceadb. In what order are the programs standing after their billion dances? Note: Not in the same spot they started :)
In [ ]:
# how long does it take to get back to original order?
dp, start = ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']
dp = ['a', 'b', 'c', 'd', 'e','f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
start = ['a', 'b', 'c', 'd', 'e','f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
# print(dp)
count = 1
while True:
for key, value in enumerate(content):
move, here, there = parseinstruction(value)
if move == 's':
dotheSpin(here)
elif move == 'x':
dotheExchange(here, there)
elif move == 'p': # they are the same in a 0-15 array
dotheExchange(here, there)
else:
print("There is a problem readint the file ", value)
if dp == start:
break
else:
count += 1
#print("AT count: ", count, dp)
print("Order of Program: ", dp)
x,y = '', ''
for i in dp:
x = x + i
print(x)
print("Dances till back to start: ", count)
In [ ]:
print("We need this many iterations more: ", 1000000000 % count)
for x in range(40):
for key, value in enumerate(content):
move, here, there = parseinstruction(value)
if move == 's':
dotheSpin(here)
elif move == 'x':
dotheExchange(here, there)
elif move == 'p': # they are the same in a 0-15 array
dotheExchange(here, there)
else:
print("There is a problem readint the file ", value)
print("Order of Program: ", dp)
What I learned
Advent of Code Day 15 - Part 1 Here, you encounter a pair of dueling generators. The generators, called generator A and generator B, are trying to agree on a sequence of numbers. However, one of them is malfunctioning, and so the sequences don't always match.
As they do this, a judge waits for each of them to generate its next value, compares the lowest 16 bits of both values, and keeps track of the number of times those parts of the values match.
The generators both work on the same principle. To create its next value, a generator will take the previous value it produced, multiply it by a factor (generator A uses 16807; generator B uses 48271), and then keep the remainder of dividing that resulting product by 2147483647. That final remainder is the value it produces next.
To calculate each generator's first value, it instead uses a specific starting value as its "previous value" (as listed in your puzzle input).
For example, suppose that for starting values, generator A uses 65, while generator B uses 8921. Then, the first five pairs of generated values are:
--Gen. A-- --Gen. B-- 1092455 430625591 1181022009 1233683848 245556042 1431495498 1744312007 137874439 1352636452 285222916 In binary, these pairs are (with generator A's value first in each pair):
00000000000100001010101101100111 00011001101010101101001100110111
01000110011001001111011100111001 01001001100010001000010110001000
00001110101000101110001101001010 01010101010100101110001101001010
01100111111110000001011011000111 00001000001101111100110000000111
01010000100111111001100000100100 00010001000000000010100000000100 Here, you can see that the lowest (here, rightmost) 16 bits of the third value match: 1110001101001010. Because of this one match, after processing these five pairs, the judge would have added only 1 to its total.
To get a significant sample, the judge would like to consider 40 million pairs. (In the example above, the judge would eventually find a total of 588 pairs that match in their lowest 16 bits.)
After 40 million pairs, what is the judge's final count?
In [ ]:
size = 40000000
afactor = 16807
bfactor = 48271
a = 65 # Sample answer 588
b = 8921 # Sample answer 588
a = 883
b = 879
diver = 2147483647
count = 0
for i in range(size):
a = (a * afactor) % diver
b = (b * bfactor) % diver
#bina = bin(a)[-16:].zfill(16)
#binb = bin(b)[-16:].zfill(16)
bina = format(a,'032b').zfill(32)[-16:]
binb = format(b,'032b').zfill(32)[-16:]
if bina== binb:
count += 1
'''
print(a, b)
print(bin(a))
print(bin(b))
print(bina)
print(binb)
'''
print("Total Pairs", count)
Advent of Code Day 15 - Part 2 In the interest of trying to align a little better, the generators get more picky about the numbers they actually give to the judge.
They still generate values in the same way, but now they only hand a value to the judge when it meets their criteria:
Generator A looks for values that are multiples of 4. Generator B looks for values that are multiples of 8. Each generator functions completely independently: they both go through values entirely on their own, only occasionally handing an acceptable value to the judge, and otherwise working through the same sequence of values as before until they find one.
The judge still waits for each generator to provide it with a value before comparing them (using the same comparison method as before). It keeps track of the order it receives values; the first values from each generator are compared, then the second values from each generator, then the third values, and so on.
Using the example starting values given above, the generators now produce the following first five values each:
--Gen. A-- --Gen. B-- 1352636452 1233683848 1992081072 862516352 530830436 1159784568 1980017072 1616057672 740335192 412269392 These values have the following corresponding binary values:
01010000100111111001100000100100 01001001100010001000010110001000
01110110101111001011111010110000 00110011011010001111010010000000
00011111101000111101010001100100 01000101001000001110100001111000
01110110000001001010100110110000 01100000010100110001010101001000
00101100001000001001111001011000 00011000100100101011101101010000 Unfortunately, even though this change makes more bits similar on average, none of these values' lowest 16 bits match. Now, it's not until the 1056th pair that the judge finds the first match:
--Gen. A-- --Gen. B-- 1023762912 896885216
00111101000001010110000111100000 00110101011101010110000111100000 This change makes the generators much slower, and the judge is getting impatient; it is now only willing to consider 5 million pairs. (Using the values from the example above, after five million pairs, the judge would eventually find a total of 309 pairs that match in their lowest 16 bits.)
After 5 million pairs, but using this new generator logic, what is the judge's final count?
In [ ]:
def findapair(aseed,bseed):
a,b = 1,1 # This so it is never true going in
while (a % 4 != 0):
a = (aseed * afactor) % diver
aseed = a
while (b % 8 != 0):
b = (bseed * bfactor) % diver
bseed = b
return(a,b)
def isabinarymatch(a, b):
bina = format(a,'032b').zfill(32)[-16:]
binb = format(b,'032b').zfill(32)[-16:]
return(bina == binb)
In [ ]:
size = 5000000
# size = 5
# size = 1058 # First match should be at 1056th
afactor = 16807
bfactor = 48271
diver = 2147483647
count, misses = 0, 0
a = 65 # Sample answer 588 and 309
b = 8921 # Sample answer 588 and 309
a = 883
b = 879
for x in range(size):
(a,b) = findapair(a,b)
# print(a,b)
if isabinarymatch(a,b):
count += 1
else:
misses += 1
print("Total Pairs", count)
print("Total Misses", misses)
What I learned